package binarysearch;

/**
 * @Description
 * @Author Firenut
 * @Date 2023-06-30 17:58
 */
public class T69_mySqrt {
    //二分法进行处理，注意变量类型
    public static double sqrt(int target) {
        double n = 1e-2;            //在这里可根据精度要求进行调整
        double l = 0, r = target;      //这里若初始化r=target/2的话，则处理较小正整数会出错，如1,2
        while (l <= r) {              //二分查找
            double mid = (l + r) / 2;
            //这里用除法，而不用mid*mid与target比较，是防止mid过大时，mid*mid产生溢出问题
            if (target / mid < mid) {
                r = mid - n;
            } else {
                l = mid + n;
            }
        }
//        return r;
        return l < target / l ? l : l - n;
    }

    public static double mySqrt(int x) {
        double n = 1e-2;
        double left, right;
        left = 0;
        right = x;
        while (left <= right) {
            double mid = left + (right - left) / 2;
            if (mid < x / mid) {
                left = mid + n;
            } else if (mid == x / mid) {
                return mid;
            } else {
                right = mid - n;
            }
        }
        return left < x/left ? left : left - n;
    }

    public static void main(String[] args) {
        //定义一个8个整数的数组来验证，数组有包括小正整数和较大的正整数
        int[] arr = {1, 2, 6, 9, 18, 65, 102, 266665898};
        for (int i = 0; i < arr.length; i++) {
            boolean res = Math.abs(mySqrt(arr[i]) - Math.sqrt(arr[i])) < 0.01;
            System.out.println("差距是否小于0.01：   " + res);                                           //达到精度要求则输出true
        }
    }
}
